package ru.susu.algebra.ranks;

import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Date;
import java.util.Map;

import ru.susu.algebra.number.MapPrimeNumbersProvider;
import ru.susu.algebra.number.PrimeNumbersProvider;
import ru.susu.algebra.util.ArrayMap;

/**
 * @author akargapolov
 * @since: 03.05.2010
 */
public class FullDPRanksCounter
{
	public static int NUMBER = 400;

	@SuppressWarnings("unchecked")
	private static ArrayMap<BitSet, BigInteger>[][][] _data = (ArrayMap<BitSet, BigInteger>[][][])Array.newInstance(ArrayMap.class, NUMBER + 3, NUMBER + 3, 4);

	private static Map<Integer, BitSet> _factors = new NumbersBitSetFactorizationProvider().performOperation(NUMBER);

	private static Map<Integer, Integer> _primes = new MapPrimeNumbersProvider().performOperation(NUMBER);

	private static Integer[] _sprimes = new PrimeNumbersProvider().performOperation(NUMBER);

	private static Map<BitSet, BitSet> _cache = new ArrayMap<BitSet, BitSet>();
	private static Map<BigInteger, BigInteger> _intcache = new ArrayMap<BigInteger, BigInteger>();

	private static long _nodes = 0;

	public static void main(String[] args) throws Exception
	{
		for (int i = 1;i <= NUMBER;i++)
		{
			Date start = new Date();
			BigInteger rank = BigInteger.ZERO;
			for (int j = 1;j<=i;j+=2)
			{
				Map<BitSet, BigInteger> map = recCounter(i, j, 0);

				for (Map.Entry<BitSet, BigInteger> entry : map.entrySet())
					if (!entry.getKey().equals(getBitSet(new BitSet(_primes.size()))))
					{
						//System.out.println(entry.getKey().toString());
						rank = rank.add(entry.getValue());
					}
			}
			freeMatrix(i - 2);

			System.out.println(recCounter(i, 1, 0).size());
			if (i % 25 == 0)
				System.gc();
			System.out.println("rank[" + i + "] - " + rank);
			System.out.println("total - " + Runtime.getRuntime().totalMemory() / 1000000);
			System.out.println("free - " + Runtime.getRuntime().freeMemory()/ 1000000);
			System.out.println("used - " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/ 1000000);
			System.out.println("nodes - " + _nodes);
			System.out.println("time - " + (new Date().getTime() - start.getTime()) + "ms");
		}

		System.out.println(_cache.size());

		Thread.sleep(120000);
	}

	protected static void freeMatrix(int i)
	{
		for (int j = 0; i - j >= 1; j += 2)
			for (int shift = 0; shift < 4; shift++)
			{
				if (_data[i - j][j + 1][shift] != null)
				{
					_nodes -= _data[i - j][j + 1][shift].size();
					_data[i - j][j + 1][shift].clear();
				}
			}
	}

	protected static ArrayMap<BitSet, BigInteger> recCounter(int i, int k, int shift)
	{
		if (_data[i][k][shift] != null)
		{
			return _data[i][k][shift];
		}
		_data[i][k][shift] = new ArrayMap<BitSet, BigInteger>();
		if (i == 0 && shift == 0)
		{
			_data[i][k][shift].put(getBitSet(new BitSet(_primes.size())), BigInteger.ONE);
		}
		else if (k < i)
		{
			for (int j = k + 2; j <= i; j+=2)
				append(_data[i][k][shift], recCounter(i - k, j, (shift + 1 - k + 4 * i) % 4), k);
		}
		else if (k == i)
		{
			append(_data[i][k][shift], recCounter(i - k, k, (shift + 1 - k + 4 * i) % 4), k);
		}
		//System.out.println(_data[i][k][shift].size());
		_nodes += _data[i][k][shift].size();
		_data[i][k][shift].trimToSize();
		_data[i][k][shift].dropIndex();
		return _data[i][k][shift];
	}

	protected static void append(ArrayMap<BitSet, BigInteger> map1, ArrayMap<BitSet, BigInteger> map2, Integer add)
	{
		ArrayList<BitSet> keys = map2.getKeys();
		ArrayList<BigInteger> values = map2.getValues();
		for (int index = 0;index < keys.size(); index++)
		{
			BitSet bitset = keys.get(index);
			if (add != null)
			{
				bitset = (BitSet)bitset.clone();
				bitset.xor(_factors.get(add));
				bitset = getBitSet(bitset);
			}
			BigInteger value = map1.get(bitset);
			if (value == null)
			{
				value = values.get(index);
			}
			else
			{
				value = value.add(values.get(index));
			}
			value = getBigInteger(value);
			map1.put(bitset, value);
		}
	}

	protected static BitSet getBitSet(BitSet bitset)
	{
		BitSet result = _cache.get(bitset);
		if (result == null)
		{
			_cache.put(bitset, bitset);
			result = bitset;
		}
		return result;
	}

	protected static BigInteger getBigInteger(BigInteger value)
	{
		BigInteger result = _intcache.get(value);
		if (result == null)
		{
			_intcache.put(value, value);
			result = value;
		}
		return result;
	}

}
